package com.sunny.l43;

public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(null == inorder || null == postorder || inorder.length != postorder.length || 0 == inorder.length)
            return null;
        return buildCore(inorder, postorder, postorder.length-1, 0,postorder.length-1);
    }

    public TreeNode buildCore(int[] inorder, int[] postorder, int ind, int left, int right){
        if(left > right)
            return null;
        if(left == right)
            return new TreeNode(inorder[left]);
        int rootInd = getInd(inorder, left, right, postorder[ind]);
        TreeNode root = new TreeNode(postorder[ind]);
        root.left = buildCore(inorder, postorder, ind-(right-rootInd)-1, left, rootInd-1);
        root.right = buildCore(inorder, postorder, ind-1, rootInd+1, right);
        return root;
    }

    public int getInd(int[] inorder, int left, int right, int val){
        int res = -1;
        for(int i=left; i<=right;i++){
            if(inorder[i] == val){
                res = i;
                break;
            }
        }
        return res;
    }

}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
